#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
typedef char Datatype;
typedef struct TrailTreeNode
{
	Datatype ch;
	struct TrailTreeNode* left;
	struct TrailTreeNode* right;
	int ltalg;
	int rtalg;
}TNode;
void TrailTree(TNode** pp, TNode** prev)
{
	if ((*pp) == NULL)
		return;


	TrailTree(&(*pp)->left,prev);
	if ((*pp)->left == NULL)
	{
	(*pp)->left = *prev;
	(*pp)->ltalg = 1;
	}
	(*pp)->ltalg = 0;
	printf("%c ", (*pp)->ch);

	if ((*prev)->right == NULL)
	{
	(*prev)->right = *pp;
	(*prev)->rtalg = 1;
	}
	(*prev)->rtalg = 0;


	*prev = *pp;


	TrailTree(&(*pp)->right, prev);
}
int main()
{
	TNode *A = (TNode *)malloc(sizeof(TNode));
	A->ch = 'A';
	A->left = NULL;
	A->right = NULL;
	TNode *B = (TNode *)malloc(sizeof(TNode));
	B->ch = 'B';
	B->left = NULL;
	B->right = NULL;
	TNode *C = (TNode *)malloc(sizeof(TNode));
	C->ch = 'C';
	C->left = NULL;
	C->right = NULL;
	TNode *D = (TNode *)malloc(sizeof(TNode));
	D->ch = 'D';
	D->left = NULL;
	D->right = NULL;
	TNode *E = (TNode *)malloc(sizeof(TNode));
	E->ch = 'E';
	E->left = NULL;
	E->right = NULL;
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	TNode *prev = (TNode *)malloc(sizeof(TNode));
	prev->right = NULL;
	TrailTree(&A, &prev);
	printf("\n");

	return 0;
}